//#define _CRT_SECURE_NO_WARNINGS 1
//
//
//class Solution {
//public:
//    string minWindow(string s, string t)
//    {
//        unordered_map<char, int> h1;
//        unordered_map<char, int> h2;
//        for (auto c : t)
//        {
//            h1[c]++;
//        }
//
//        int left = 0, right = 0;
//        int n = s.size();
//        int n2 = t.size();
//        int begin = 0, len = INT_MAX;
//
//        int count = 0;
//        while (right < n)
//        {
//            char in = s[right];
//            if (h1.count(in))
//            {
//                if (++h2[in] <= h1[in]) count++;
//            }
//
//            while (count == n2)
//            {
//                if (len > right - left + 1)
//                {
//                    begin = left;
//                    len = right - left + 1;
//                }
//
//                char out = s[left++];
//                if (h1.count(out))
//                {
//                    if (--h2[out] < h1[out]) count--;
//                }
//            }
//            right++;
//        }
//
//        return len == INT_MAX ? "" : s.substr(begin, len);
//    }
//};
//
//
//class Solution {
//public:
//    vector<int> maxSlidingWindow(vector<int>& nums, int k)
//    {
//        vector<int> ret;
//        int right = 0, left = 0;
//        int n = nums.size();
//        priority_queue<pair<int, int>> pq;
//        while (right < n)
//        {
//            pq.push({ nums[right],right });
//
//            if (pq.size() > k)
//            {
//                left++;
//                while (pq.top().second < left)
//                {
//                    pq.pop();
//                }
//            }
//
//            if (pq.size() >= k)
//            {
//                ret.push_back(pq.top().first);
//            }
//            right++;
//        }
//        return ret;
//    }
//};
//
//
//class Solution {
//public:
//    int subarraySum(vector<int>& nums, int k)
//    {
//        int n = nums.size();
//        unordered_map<int, int> h;
//        vector<int> sum(n + 1);
//
//        h[0] = 1;
//        int ret = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            sum[i] = sum[i - 1] + nums[i - 1];
//            if (h.count(sum[i] - k))
//            {
//                ret += h[sum[i] - k];
//            }
//            h[sum[i]]++;
//        }
//
//        return ret;
//    }
//};
//
//
//class Solution {
//public:
//    vector<int> findAnagrams(string s, string p)
//    {
//        int h1[26] = { 0 };
//        int h2[26] = { 0 };
//        for (auto c : p)
//        {
//            h1[c - 'a']++;
//        }
//
//        int left = 0, right = 0, count = 0;
//        int n = s.size();
//        int len = p.size();
//        vector<int> ret;
//        while (right < n)
//        {
//            char in = s[right];
//            if (h1[in - 'a'] > 0)
//            {
//                if (++h2[in - 'a'] <= h1[in - 'a']) count++;
//            }
//
//            while (right - left + 1 > len)
//            {
//                char out = s[left++];
//                if (h1[out - 'a'] > 0)
//                {
//                    if (--h2[out - 'a'] < h1[out - 'a']) count--;
//                }
//            }
//            if (count == len) ret.push_back(left);
//
//            right++;
//        }
//
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    int lengthOfLongestSubstring(string s)
//    {
//        int ret = 0;
//        int h[128] = { 0 };
//        int left = 0, right = 0;
//
//        int n = s.size();
//        while (right < n)
//        {
//            char in = s[right];
//            h[in]++;
//            while (h[in] > 1)
//            {
//                char out = s[left++];
//                h[out]--;
//            }
//            ret = max(right - left + 1, ret);
//            right++;
//        }
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    int trap(vector<int>& height)
//    {
//        int n = height.size();
//        vector<int> heightl(n);
//        vector<int> heightr(n);
//        for (int i = 1; i < n; i++)
//        {
//            heightl[i] = max(heightl[i - 1], height[i - 1]);
//        }
//
//        for (int i = n - 2; i >= 0; i--)
//        {
//            heightr[i] = max(heightr[i + 1], height[i + 1]);
//        }
//
//        int ret = 0;
//        for (int i = 0; i < n; i++)
//        {
//            int lefth = heightl[i];
//            int righth = heightr[i];
//            int h = min(lefth, righth);
//            ret += max(0, h - height[i]);
//        }
//
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums)
//    {
//        sort(nums.begin(), nums.end());
//        int n = nums.size();
//        vector<vector<int>> ret;
//        for (int i = 0; i < n;)
//        {
//            if (nums[i] > 0) break;
//            int target = -nums[i];
//            int left = i + 1, right = n - 1;
//            while (left < right)
//            {
//                if (nums[left] + nums[right] == target)
//                {
//                    ret.push_back({ nums[i],nums[left++],nums[right--] });
//                    while (left < right && nums[left] == nums[left - 1])
//                    {
//                        left++;
//                    }
//                    while (left < right && nums[right] == nums[right + 1])
//                    {
//                        right--;
//                    }
//                }
//                else if (nums[left] + nums[right] > target)
//                {
//                    right--;
//                }
//                else
//                {
//                    left++;
//                }
//            }
//            i++;
//            while (i < n && nums[i] == nums[i - 1])
//            {
//                i++;
//            }
//        }
//
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    int maxArea(vector<int>& height)
//    {
//        int left = 0, right = height.size() - 1;
//        int ret = 0;
//        while (left < right)
//        {
//            int len = right - left;
//            int wid = min(height[left], height[right]);
//            ret = max(ret, len * wid);
//            if (height[left] < height[right]) left++;
//            else right--;
//        }
//
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    void moveZeroes(vector<int>& nums)
//    {
//        int left = -1, right = 0;
//        int n = nums.size();
//        while (right < n)
//        {
//            if (nums[right] != 0)
//            {
//                swap(nums[right], nums[++left]); a
//            }
//            right++;
//        }
//    }
//};
//
//class Solution {
//public:
//    vector<vector<string>> groupAnagrams(vector<string>& strs)
//    {
//        unordered_map<string, int> h;
//        int n = strs.size();
//        vector<vector<string>> ret;
//        int i = 0;
//        for (auto& str : strs)
//        {
//            string s = str;
//            sort(s.begin(), s.end());
//            if (!h.count(s))
//            {
//                ret.push_back({ str });
//                h[s] = i++;
//            }
//            else
//            {
//                ret[h[s]].push_back(str);
//            }
//        }
//
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    int longestConsecutive(vector<int>& nums)
//    {
//        unordered_set<int> h;
//        for (auto c : nums)
//        {
//            h.insert(c);
//        }
//
//        int ret = 0;
//
//        for (auto e : h)
//        {
//            if (!h.count(e - 1))
//            {
//                int num = e;
//                int len = 1;
//                while (h.count(num + 1))
//                {
//                    num++;
//                    len++;
//                }
//
//                ret = max(ret, len);
//            }
//        }
//
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    typedef long long LL;
//    vector<int> twoSum(vector<int>& nums, int target)
//    {
//        int n = nums.size();
//        unordered_map<int, int> h;
//        for (int i = 0; i < n; i++)
//        {
//            LL tmp = target - nums[i];
//            if (h.count(tmp))
//            {
//                return { h[tmp],i };
//            }
//            else
//            {
//                h[nums[i]] = i;
//            }
//        }
//
//        return { -1,-1 };
//    }
//};